package leetcode.D100.T53;

class Solution {
    // 一刷
    /*public int maxSubArray(int[] nums) {
        int[] dp = Arrays.copyOf(nums, nums.length);
        for(int i=1; i<nums.length; ++i) {
            dp[i] = Math.max(dp[i], nums[i]+dp[i-1]);
        }
        int maxNum = Integer.MIN_VALUE;
        for(int i=0; i<dp.length; ++i) {
            maxNum = Math.max(maxNum, dp[i]);
        }
        return maxNum;
    }*/

    // 二刷
    /*public int maxSubArray(int[] nums) {
        int sum = nums[0], result = nums[0];
        for(int i=1; i<nums.length; ++i) {
            sum = Math.max(nums[i], nums[i] + sum);
            result = Math.max(result, sum);
        }
        return result;
    }*/

    // 三刷
    public int maxSubArray(int[] nums) {
        int result = nums[0], sum = nums[0];
        for (int i=1; i<nums.length; ++i) {
            sum = Math.max(nums[i], nums[i] + sum);
            result = Math.max(result, sum);
        }
        return result;
    }
}